11. CODE: Adding Nodes to the Open Vector

Adding Nodes to the Open Vector

Writing the `AddToOpen()` function

Writing the AddToOpen() function

As you've seen from Sebastian's explanation of A* search, the search algorithm keeps a list of potential board cells to search through. In this implementation of A*, we will refer to a board cell along with it's g and h values as a node. In other words, each node will consist of the following values which are needed for the A* algorithm:

  • an x coordinate,
  • a y coordinate,
  • the g value (or cost) that has accumulated up to that cell,
  • the h value for the cell, given by the heuristic function.

In the code, nodes will be implemented with the type vector<int>, and should have the form {x, y, g, h} for ints x, y, g, and h. Also, the open list will be implemented as a C++ vector (of type vector<vector<int>>). The goal in this exercise is for you to write a helper function for your A* Search which will add nodes to the open vector and mark them as visited in the grid.

To Complete This Exercise:

  1. Write a void AddToOpen function which accepts the following arguments:
    • Four ints, one for each of the x, y, g, and h values.
    • References to one vector<vector<int>> for the vector of open nodes.
    • Reference to one vector<vector<State>> for the grid.
  2. The AddToOpen function should do two things:
    • Create a vector<int> node with the form {x, y, g, h} and push the node to the back of the open vector.
    • Set the grid value for the x and y coordinates to the enum value kClosed. We have added kClosed to the set of enum values.

Workspace

This section contains either a workspace (it can be a Jupyter Notebook workspace or an online code editor work space, etc.) and it cannot be automatically downloaded to be generated here. Please access the classroom with your account and manually download the workspace to your local machine. Note that for some courses, Udacity upload the workspace files onto https://github.com/udacity, so you may be able to download them there.

Workspace Information:

  • Default file path:
  • Workspace type: generic
  • Opened files (when workspace is loaded): n/a
  • userCode:

    export CXX=g++-7
    export CXXFLAGS=-std=c++17
    g++() {
    /usr/bin/g++-7 -std=c++17 "$1"
    }
    export -f g++

Next Concept